package com.test.sort;

import java.util.Random;

/**
 * 奇偶交换排序串行排序
 * 
 * @author xuguangqiao
 *
 */
public class OddEventSort {

	public static int[] oddEventSort(int[] arr) {
		int exchFlag = 1, start = 0;
		while (exchFlag == 1 || start == 1) {
			exchFlag = 0;
			for (int i = start; i < arr.length - 1; i += 2) {
				if (arr[i] > arr[i + 1]) {
					int temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
					exchFlag = 1;
				}
			}
			if (start == 0) {
				start = 1;
			} else {
				start = 0;
			}
		}
		return arr;
	}

	public static void main(String[] args) {
		// int arr[] = {44,4,6,2,8,3,1,65,6,7,42,12,4,236,9,63,3};
		int len = 100000;
		int[] arr = new int[len];
		Random random = new Random();
		for (int i = 0; i < arr.length; i++) {
			arr[i] = random.nextInt(100000);
		}
		long start = System.currentTimeMillis();
		oddEventSort(arr);
		//maoPoSort(arr);
		long end = System.currentTimeMillis();
		System.out.println(end - start);
		//System.out.println(Arrays.toString(sort(arr)));
	}

	/**
	 * 冒泡排序
	 * 
	 * @param arr
	 * @return
	 */
	public static int[] maoPoSort(int[] arr) {

		for (int i = 0; i < arr.length; i++) {
			int temp;
			for (int j = i + 1; j < arr.length-1; j++) {
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
		return arr;
	}
}
